<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title>Trees</title>

<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link rel="stylesheet" href="theme/style.css" type="text/css"></head>
<body>
<table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
  <tbody><tr>
    <td width="10">
    <br>
</td>
    <td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Trees</b></font>
    </td>
    <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
  </tr>
</tbody></table>
<br>
<table border="0">
  <tbody><tr>
    <td width="10"><br>
</td>
    <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
    <td width="30"><a href="symbols.html"><img src="theme/l_arr.gif" border="0"></a></td>
    <td width="30"><a href="multi_pass.html"><img src="theme/r_arr.gif" border="0"></a></td>
   </tr>
</tbody></table>
<h2>Why use parse trees</h2>
<p> Parse trees are an in-memory representation of the input with a structure
  that conforms to the grammar.</p>
<p> The advantages of using parse trees instead of semantic actions:</p>
<ul>
  <li>You can make multiple passes over the data without having to re-parse the
    input.</li>
  <li>You can perform transformations on the tree.</li>
  <li>You can evaluate things in any order you want, whereas with attribute schemes
    you have to process in a begin to end fashion.</li>
  <li>You do not have to worry about backtracking and action side effects that
    may occur with an ambiguous grammar.</li>
</ul>
<p> <b>Example</b></p>
<p> Now that you think you may want to use trees, I'll give an example of how
  to use them and you can see how easy they are to use. So, following with tradition
  (and the rest of the documentation) we'll do a calculator. Here's the grammar:</p>
<pre>    <code><span class="identifier">integer </span><span class="special">
        =   </span><span class="identifier"><font color="#ff0000"><b>token_node_d</b></font></span><span class="special">[ (!</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">) &gt;&gt; +</span><span class="identifier">digit_p</span><span class="special">) ]<br>        ;<br><br>    </span><span class="identifier">factor<br>        </span><span class="special">=   </span><span class="identifier">integer<br>        </span><span class="special">|   </span><span class="literal">'(' </span><span class="special">&gt;&gt; </span><span class="identifier">expression </span><span class="special">&gt;&gt; </span><span class="literal">')'<br>        </span><span class="special">|   (</span><span class="literal">'-' </span><span class="special">&gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>        ;<br><br>    </span><span class="identifier">term<br>        </span><span class="special">=   </span><span class="identifier">factor </span><span class="special">
            &gt;&gt; *(   (</span><span class="literal">'*' </span><span class="special">&gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>                |   (</span><span class="literal">'/' </span><span class="special">&gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>                )<br>        ;<br><br>    </span><span class="identifier">expression<br>        </span><span class="special">=   </span><span class="identifier">term<br>            </span><span class="special">&gt;&gt; *(   (</span><span class="literal">'+' </span><span class="special">&gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                |   (</span><span class="literal">'-' </span><span class="special">&gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                )<br>        ;</span></code></pre>
<p> Now, you'll notice the only thing different in this grammar is the <tt>token_node_d</tt>
  directive. This causes the match of the integer rule to end up in one node.
  Without <tt>token_node_d</tt>, each character would get it's own node. 
  Further note that <tt>token_node_d</tt> is an implicit lexeme (that means
  no <tt>lexeme_d</tt> is needed to switch to character level parsing).
  As you'll soon see, it's easier to convert the input into an int when all 
  the characters are in one node. Here is how the parse is done to create a tree:</p>
<pre>    <code><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt; </span><span class="identifier">info </span><span class="special">= </span><span class="identifier"><font color="#ff0000"><b>pt_parse</b></font></span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">expression</span><span class="special">);</span></code></pre>
<p> <tt>pt_parse()</tt> is similar to <tt>parse()</tt>. There are four overloads:
  two for pairs of first and last iterators and two for character strings. Two
  of the functions take a skipper parser and the other two do not.</p>
<p> The <tt>tree_parse_info</tt> struct contains the same information as a <tt>parse_info</tt>
  struct as well as one extra data member called trees. When the parse finishes,
  trees will contain the parse tree.</p>
<p> Here is how you can use the tree to evaluate the input:</p>
<pre>    <code><span class="keyword">if </span><span class="special">(</span><span class="identifier">info</span><span class="special">.</span><span class="identifier">full</span><span class="special">)<br>    {<br>        </span><span class="identifier">cout </span><span class="special">&lt;&lt; </span><span class="string">"parsing succeeded\n"</span><span class="special">;<br>        </span><span class="identifier">cout </span><span class="special">&lt;&lt; </span><span class="string">"result = " </span><span class="special">&lt;&lt; </span><span class="identifier"><font color="#ff0000"><b>evaluate</b></font></span><span class="special">(</span><span class="identifier">info</span><span class="special">) &lt;&lt; </span><span class="string">"\n\n"</span><span class="special">;<br>    }</span></code></pre>
<p> Now you ask, where did <tt>evaluate()</tt> come from? Is it part of spirit?
  Unfortunately, no, <tt>evaluate()</tt> is only a part of the sample. Here it
  is:</p>
<pre>    <code><span class="keyword">long </span><span class="identifier">evaluate</span><span class="special">(</span><span class="keyword">const </span><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt;&amp; </span><span class="identifier">info</span><span class="special">)<br>    </span><span class="special">{<br>        </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">info</span><span class="special">.</span><span class="identifier">trees</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br>    </span><span class="special">}</span></code></pre>
<p> So here you see evaluate() simply calls <tt>eval_expression()</tt> passing
  the begin() iterator of info.trees. Now here's the rest of the example:</p>
<pre>    <code><span class="comment">// Here's some typedefs to simplify things<br>    </span><span class="keyword">typedef char const</span><span class="special">*                              </span><span class="identifier">iterator_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special">&lt;</span><span class="identifier">iterator_t</span><span class="special">&gt;             </span><span class="identifier">      parse_tree_match_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">parse_tree_match_t</span><span class="special">::</span><span class="identifier">const_tree_iterator  iter_t</span><span class="special">;<br><br>    </span><span class="comment">// Here's the function prototypes that we'll use.  One function for each<br>    // grammar rule</span><span class="special">.<br>    </span><span class="keyword">long </span><span class="identifier">evaluate</span><span class="special">(</span><span class="keyword">const </span><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt;&amp; </span><span class="identifier">info</span><span class="special">);<br>    </span><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">);<br>    </span><span class="keyword">long </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">);<br>    </span><span class="keyword">long </span><span class="identifier">eval_factor</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">);<br>    </span><span class="keyword">long </span><span class="identifier">eval_integer</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">);<br><br>    </span><span class="comment">// i should be pointing to a node created by the expression rule<br>    </span><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">)<br>    {<br>        </span><span class="comment">// first child points to a term, so call eval_term on it<br>        </span><span class="identifier">iter_t chi </span><span class="special">= </span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();<br>        </span><span class="keyword">long </span><span class="identifier">lhs </span><span class="special">= </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">chi</span><span class="special">);<br>        </span><span class="keyword">for </span><span class="special">(++</span><span class="identifier">chi</span><span class="special">; </span><span class="identifier">chi </span><span class="special">!= </span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">end</span><span class="special">(); ++</span><span class="identifier">chi</span><span class="special">)<br>        {<br>            </span><span class="comment">// next node points to the operator.  The text of the operator is<br>            // stored in value (a vector&lt;char&gt;)<br>            </span><span class="keyword">char </span><span class="identifier">op </span><span class="special">= *(</span><span class="identifier">chi</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br>            ++</span><span class="identifier">chi</span><span class="special">;<br>            </span><span class="keyword">long </span><span class="identifier">rhs </span><span class="special">= </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">chi</span><span class="special">);<br>            </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">op </span><span class="special">== </span><span class="literal">'+'</span><span class="special">)<br>                </span><span class="identifier">lhs </span><span class="special">+= </span><span class="identifier">rhs</span><span class="special">;<br>            </span><span class="keyword">else if </span><span class="special">(</span><span class="identifier">op </span><span class="special">== </span><span class="literal">'-'</span><span class="special">)<br>                </span><span class="identifier">lhs </span><span class="special">-= </span><span class="identifier">rhs</span><span class="special">;<br>            </span><span class="keyword">else<br>                </span><span class="identifier">assert</span><span class="special">(</span><span class="number">0</span><span class="special">);<br>        }<br>        </span><span class="keyword">return </span><span class="identifier">lhs</span><span class="special">;<br>    }<br><br>    </span><span class="keyword">long </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">)<br>    {<br>        </span><span class="comment">//  ... see <a href="../example/fundamental/parse_tree_calc1.cpp">parse_tree_calc1.cpp</a> for complete example<br>        //  (it's rather similar to eval_expression() ) ...<br>    </span><span class="special">}<br><br>    </span><span class="keyword">long </span><span class="identifier">eval_factor</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">)<br>    {<br>        </span><span class="comment">//  ... again, see <a href="../example/fundamental/parse_tree_calc1.cpp">parse_tree_calc1.cpp</a> if you want all the details ...<br>    </span><span class="special">}<br><br>    </span><span class="keyword">long </span><span class="identifier">eval_integer</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">)<br>    </span><span class="special">{<br>        </span><span class="comment">// use the range constructor for a string<br>        </span><span class="identifier">string </span><span class="identifier">integer</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(), </span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">end</span><span class="special">());<br>        </span><span class="comment">// convert the string to an integer<br>        </span><span class="keyword">return </span><span class="identifier">strtol</span><span class="special">(</span><span class="identifier">integer</span><span class="special">.</span><span class="identifier">c_str</span><span class="special">(), </span><span class="number">0</span><span class="special">, </span><span class="number">10</span><span class="special">);<br>    </span><span class="special">}<br></span></code></pre>
<p>  <img height="16" width="15" src="theme/lens.gif"> The full source code can be <a href="../example/fundamental/parse_tree_calc1.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
<p>So, you like what you see, but maybe you think that the parse tree is too
    hard to process? With a few more directives you can generate an abstract syntax
    tree (ast) and cut the amount of evaluation code by at least <b>50%</b>. So
    without any delay, here's the ast calculator grammar:</p>
<pre>    <code><span class="identifier">integer<br>        </span><span class="special">=   </span><span class="identifier"><font color="#ff0000"><b>leaf_node_d</b></font></span><span class="special">[ </span><span class="special">(!</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">) &gt;&gt; +</span><span class="identifier">digit_p</span><span class="special">) ]<br>        ;<br><br>    </span><span class="identifier">factor<br>        </span><span class="special">=   </span><span class="identifier">integer<br>        </span><span class="special">|   </span><span class="identifier"><font color="#ff0000"><b>inner_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'('</span><span class="special">) &gt;&gt; </span><span class="identifier">expression </span><span class="special">&gt;&gt; </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">')'</span><span class="special">)]<br>        |   (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">)] &gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>        ;<br><br>    </span><span class="identifier">term<br>        </span><span class="special">=   </span><span class="identifier">factor </span><span class="special">
            &gt;&gt; *(  (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'*'</span><span class="special">)] &gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>                |  (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'/'</span><span class="special">)] &gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>                )<br>        ;<br><br>    </span><span class="identifier">expression<br>        </span><span class="special">=   </span><span class="identifier">term<br>            </span><span class="special">&gt;&gt; *(  (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'+'</span><span class="special">)] &gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">)] &gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                )<br>        ;</span></code></pre>
<p> The differences from the parse tree grammar are hi-lighted in <b><font color="#ff0000">bold-red</font></b>.
  The <tt>inner_node_d</tt> directive causes the first and last nodes generated
  by the enclosed parser to be discarded, since we don't really care about the
  parentheses when evaluating the expression. The <tt>root_node_d</tt> directive
  is the key to ast generation. A node that is generated by the parser inside
  of <tt>root_node_d</tt> is marked as a root node. When a root node is created,
  it becomes a root or parent node of the other nodes generated by the same rule.</p>
<p> To start the parse and generate the ast, you must use the ast_parse functions,
  which are similar to the pt_parse functions.</p>
<pre>    <code><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt; </span><span class="identifier">info </span><span class="special">= </span><span class="identifier">ast_parse</span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">expression</span><span class="special">);</span></code></pre>
<p> Here is the eval_expression function (note that to process the ast we only
  need one function instead of four):</p>
<pre>    <code><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">i</span><span class="special">)<br>    </span><span class="special">{<br>        </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&amp;</span><span class="identifier">integer</span><span class="special">))<br>        </span><span class="special">{<br>            </span><span class="comment">// convert string to integer<br>            </span><span class="identifier">string </span><span class="identifier">integer</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(), </span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">end</span><span class="special">());<br>            </span><span class="keyword">return </span><span class="identifier">strtol</span><span class="special">(</span><span class="identifier">integer</span><span class="special">.</span><span class="identifier">c_str</span><span class="special">(), </span><span class="number">0</span><span class="special">, </span><span class="number">10</span><span class="special">);<br>        </span><span class="special">}<br>        </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&amp;</span><span class="identifier">factor</span><span class="special">))<br>        </span><span class="special">{<br>            </span><span class="comment">// factor can only be unary minus<br>            </span><span class="keyword">return </span><span class="special">- </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br>        </span><span class="special">}<br>        </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&amp;</span><span class="identifier">term</span><span class="special">))<br>        </span><span class="special">{<br>            </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'*'</span><span class="special">)<br>            </span><span class="special">{<br>                </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">*<br>                    </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br>            </span><span class="special">}<br>            </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'/'</span><span class="special">)<br>            </span><span class="special">{<br>                </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">/<br>                    </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br>            </span><span class="special">}<br>        </span><span class="special">}<br>        </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&amp;</span><span class="identifier">expression</span><span class="special">))<br>        </span><span class="special">{<br>            </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'+'</span><span class="special">)<br>            </span><span class="special">{<br>                </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">+<br>                    </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br>            </span><span class="special">}<br>            </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'-'</span><span class="special">)<br>            </span><span class="special">{<br>                </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">-<br>                    </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br>            </span><span class="special">}<br>        </span><span class="special">}<br><br>        </span><span class="keyword">return </span><span class="number">0</span><span class="special">;<br>    </span><span class="special">}<br></span></code></pre>
<p> <img src="theme/lens.gif" width="15" height="16"> An entire working example is <a href="../example/fundamental/ast_calc.cpp">ast_calc.cpp</a>. Hopefully this example has been enough to whet your appetite for 
  trees. For more nitty-gritty details, keep on reading the rest of this chapter.</p>
<a name="usage"></a>
<h2>Usage</h2>
<a name="pt_parse"></a>
<h3>pt_parse</h3>
<p> To create a parse tree, you can call one of the five free functions:</p>
<pre>    <span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>FactoryT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>, </span><span class=identifier>FactoryT</span><span class=special>&gt;    <br>    </span><span class=identifier>pt_parse</span><span class=special>(        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>,
        </span><span class="identifier">FactoryT</span><span class=special> </span><span class="keyword">const</span><span class=special> &amp;        </span><span class="identifier">factory_</span><span class=special> = </span><span class="identifier">FactoryT</span><span class=special>());    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <br>    </span><span class=identifier>pt_parse</span><span class=special>(        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <br>    </span><span class=identifier>pt_parse</span><span class=special>(        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <br>    </span><span class=identifier>pt_parse</span><span class=special>(        <br>        </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*            </span><span class=identifier>str</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <br>    </span><span class=identifier>pt_parse</span><span class=special>(        <br>        </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*            </span><span class=identifier>str</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);<br></span></pre>
<a name="ast_parse"></a>
<h3>ast_parse</h3>
<p> To create an abstract syntax tree (ast for short) you call one of the five
  free functions:</p>
<pre>    <span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>FactoryT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>, </span><span class=identifier>FactoryT</span><span class=special>&gt;    <br>    </span><span class=identifier>ast_parse</span><span class=special>(        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>,
       </span><span class="identifier"> FactoryT</span><span class=special> </span><span class="keyword">const</span><span class=special> &amp;        </span><span class="identifier">factory_</span><span class=special> = </span><span class="identifier">FactoryT</span><span class=special>()</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <br>    </span><span class=identifier>ast_parse</span><span class=special>(        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <br>    </span><span class=identifier>ast_parse</span><span class=special>(        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <br>    </span><span class=identifier>ast_parse</span><span class=special>(        <br>        </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*            </span><span class=identifier>str</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <br>    </span><span class=identifier>ast_parse</span><span class=special>(        <br>        </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*            </span><span class=identifier>str</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);<br></span></pre>
<a name="tree_parse_info"></a> 
<h3>tree_parse_info</h3>
<p> The <tt>tree_parse_info</tt> struct returned from pt_parse and ast_parse contains 
  information about the parse:</p>
<pre>    <code><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*&gt;<br>    </span><span class="keyword">struct </span><span class="identifier">tree_parse_info<br>    </span><span class="special">{<br>        </span><span class="identifier">IteratorT   </span><span class="identifier">stop</span><span class="special">;<br>        </span><span class="keyword">bool        </span><span class="identifier">match</span><span class="special">;<br>        </span><span class="keyword">bool        </span><span class="identifier">full</span><span class="special">;<br>        </span><span class="keyword">std::size_t </span><span class="identifier">length</span><span class="special">;<br><br>        </span><span class="keyword">typename </span><span class="identifier">tree_match</span><span class="special">&lt;</span><span class="identifier">IteratorT</span><span class="special">&gt;::</span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br>    </span><span class="special">};<br></span></code></pre>
<table width="90%" border="0" align="center">
  <tbody><tr>
    <td class="table_title" colspan="10"> tree_parse_info </td>
  </tr>
  <tr>
  </tr><tr>
    <td class="table_cells"><b>stop</b></td>
    <td class="table_cells">points to the final parse position (i.e. parsing processed
      the input up to this point).</td>
  </tr>
  <tr><td class="table_cells"><b>match</b></td>
  <td class="table_cells">true if parsing is successful. This may be full (the
    parser consumed all the input), or partial (the parser consumed only a portion
    of the input.)</td>
  </tr>
  <tr><td class="table_cells"><b>full</b></td>
  <td class="table_cells">true when we have a full match (when the parser consumed
    all the input).</td>
  </tr>
  <tr><td class="table_cells"><b>length</b></td>
  <td class="table_cells">The number of characters consumed by the parser. This
    is valid only if we have a successful match (either partial or full).</td>
  </tr>
  <tr><td class="table_cells"><b>trees</b></td>
  <td class="table_cells">Contains the root node(s) of the tree.</td>
  </tr>
</tbody></table>
<a name="tree_match"></a>
<h3>tree_match</h3>
<p> When Spirit is generating a tree, the parser's parse() member function will 
  return a tree_match object, instead of a match object. tree_match has three 
  template parameters. The first is the Iterator type which defaults to <tt>char 
  const*</tt>. The second is the node factory, which defaults to <a href="#node_val_data_factory">node_val_data_factory</a>. 
  The third is the attribute type stored in the match. A tree_match has a member 
  variable which is a container (a <tt>std::vector</tt>) of <a href="#tree_node">tree_node</a> 
  objects named trees. For efficiency reasons, when a tree_match is copied, the 
  trees are <b>not</b> copied, they are moved to the new object, and the source 
  object is left with an empty tree container. tree_match supports the same interface 
  as the match class: it has an operator bool() so you can test it for a successful 
  match: if (matched), and you can query the match length via the length() function. 
  The class has this interface:</p>
<pre>    <code><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*, </span><span class="keyword">typename </span><span class="identifier">NodeFactoryT </span><span class="special">= </span><span class="identifier">node_val_data_factory</span><span class="special">&lt;&gt; </span><span class="special">&gt;<br>    </span><span class="keyword">struct </span><span class="identifier">tree_match<br>    </span><span class="special">{<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">NodeFactoryT</span><span class="special">::</span><span class="keyword">template </span><span class="identifier">factory</span><span class="special">&lt;</span><span class="identifier">IteratorT</span><span class="special">&gt; </span><span class="identifier">node_factory_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">node_factory_t</span><span class="special">::</span><span class="identifier">node_t                    </span><span class="identifier">parse_node_t</span><span class="special">;<br>        </span><span class="keyword">typedef          </span><span class="identifier">tree_node</span><span class="special">&lt;</span><span class="identifier">parse_node_t</span><span class="special">&gt;                   </span><span class="identifier">node_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">node_t</span><span class="special">::</span><span class="identifier">children_t                        </span><span class="identifier">container_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator                     </span><span class="identifier">tree_iterator</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator               </span><span class="identifier">const_tree_iterator</span><span class="special">;<br><br>        </span><span class="identifier">tree_match</span><span class="special">();<br>        </span><span class="identifier">tree_match</span><span class="special">(</span><span class="keyword">std::size_t </span><span class="identifier">length</span><span class="special">, </span><span class="identifier">parse_node_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">n</span><span class="special">);<br>        </span><span class="identifier">tree_match</span><span class="special">(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">x</span><span class="special">);<br>        </span><span class="keyword">explicit </span><span class="identifier">tree_match</span><span class="special">(</span><span class="identifier">match </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">x</span><span class="special">);<br>        </span><span class="identifier">tree_match</span><span class="special">&amp; </span><span class="keyword">operator</span><span class="special">=(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">x</span><span class="special">);<br>        </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">tree_match</span><span class="special">&amp; </span><span class="identifier">x</span><span class="special">);<br>        </span><span class="keyword">operator </span><span class="keyword">bool</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br>        </span><span class="keyword">int </span><span class="identifier">length</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br><br>        </span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br>    </span><span class="special">};</span></code></pre>
<p> When a parse has successfully completed, the trees data member will contain 
  the root node of the tree. </p>
<table width="80%" border="0" align="center">
  <tbody><tr> 
    <td class="note_box"><img src="theme/lens.gif" width="15" height="16"> <b>vector?</b><br>
      <br>
      You may wonder, why is it a vector then? The answer is that it is partly 
      for implementation purposes, and also if you do not use any rules in your 
      grammar, then trees will contain a sequence of nodes that will not have 
      any children.</td>
  </tr>
</tbody></table>
<p> Having spirit create a tree is similar to how a normal parse is done:</p>
<pre>    <code><span class="identifier">tree_match</span><span class="special">&lt;&gt; </span><span class="identifier">hit </span><span class="special">= </span><span class="identifier">expression</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">tree_scanner</span><span class="special">);<br><br>    </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">hit</span><span class="special">)<br>        </span><span class="identifier">process_tree_root</span><span class="special">(</span><span class="identifier">hit</span><span class="special">.</span><span class="identifier">trees</span><span class="special">[</span><span class="number">0</span><span class="special">]); </span><span class="comment">// do something with the tree</span></code></pre>
<a name="tree_node"></a>
<h3>tree_node</h3>
<p> Once you have created a tree by calling <a href="#pt_parse">pt_parse</a>
  or <a href="#ast_parse">ast_parse</a>, you have a <a href="#tree_parse_info">tree_parse_info</a>
  which contains the root node of the tree, and now you need to do something with
  the tree. The data member trees of <a href="#tree_parse_info">tree_parse_info</a>
  is a std::vector&lt;tree_node&gt;. tree_node provides the tree structure. The
  class has one template parameter named T. tree_node contains an instance of
  type T. It also contains a std::vector&lt;tree_node&lt;T&gt; &gt; which are
  the node's children. The class looks like this:</p>
<pre>    <code><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">T</span><span class="special">&gt;<br>    </span><span class="keyword">struct </span><span class="identifier">tree_node<br>    </span><span class="special">{<br>        </span><span class="keyword">typedef </span><span class="identifier">T </span><span class="identifier">parse_node_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">tree_node</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt; </span><span class="special">&gt; </span><span class="identifier">children_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">children_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">tree_iterator</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">children_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_tree_iterator</span><span class="special">;<br><br>        </span><span class="identifier">T </span><span class="identifier">value</span><span class="special">;<br>        </span><span class="identifier">children_t </span><span class="identifier">children</span><span class="special">;<br><br>        </span><span class="identifier">tree_node</span><span class="special">();<br>        </span><span class="keyword">explicit </span><span class="identifier">tree_node</span><span class="special">(</span><span class="identifier">T </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">v</span><span class="special">);<br>        </span><span class="identifier">tree_node</span><span class="special">(</span><span class="identifier">T </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">v</span><span class="special">, </span><span class="identifier">children_t </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">c</span><span class="special">);<br>        </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">tree_node</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;&amp; </span><span class="identifier">x</span><span class="special">);<br>    </span><span class="special">};</span></code></pre>
<p> This class is simply used to separate the tree framework from the data stored 
  in the tree. It is a generic node and any type can be stored inside it and acessed 
  via the data member value. The default type for T is <tt>node_val_data</tt>.</p>
<a name="node_val_data"></a>
<h3>node_val_data</h3>
<p> The <tt>node_val_data</tt> class contains the actual information about each 
  node. This includes the text or token sequence that was parsed, an <tt>id</tt> 
  that indicates which rule created the node, a boolean flag that indicates whether 
  the node was marked as a root node, and an optional user-specified value. This 
  is the interface:</p>
<pre>    <code><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*, </span><span class="keyword">typename </span><span class="identifier">ValueT </span><span class="special">= </span><span class="identifier">nil_t</span><span class="special">&gt;<br>    </span><span class="keyword">struct </span><span class="identifier">node_val_data<br>    </span><span class="special">{<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special">&lt;</span><span class="identifier">IteratorT</span><span class="special">&gt;::</span><span class="identifier">value_type </span><span class="identifier">value_type</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">value_type</span><span class="special">&gt; </span><span class="identifier">container_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">iterator_t</span><span class="special">;<br>        </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_iterator_t</span><span class="special">;<br><br>        </span><span class="identifier">node_val_data</span><span class="special">();<br>        </span><span class="identifier">node_val_data</span><span class="special">(</span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">_last</span><span class="special">);<br>        </span><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT2</span><span class="special">&gt;<br>        </span><span class="identifier">node_val_data</span><span class="special">(</span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">_last</span><span class="special">);<br>        </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">node_val_data</span><span class="special">&amp; </span><span class="identifier">x</span><span class="special">);<br><br>        </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">begin</span><span class="special">();<br>        </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">begin</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br>        </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">end</span><span class="special">();<br>        </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">end</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br><br>        </span><span class="keyword">bool </span><span class="identifier">is_root</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br>        </span><span class="keyword">void </span><span class="identifier">is_root</span><span class="special">(</span><span class="keyword">bool </span><span class="identifier">b</span><span class="special">);<br><br>        </span><span class="identifier">parser_id </span><span class="identifier">id</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br>        </span><span class="keyword">void </span><span class="identifier">id</span><span class="special">(</span><span class="identifier">parser_id </span><span class="identifier">r</span><span class="special">);<br><br>        </span><span class="identifier">ValueT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">value</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br>        </span><span class="keyword">void </span><span class="identifier">value</span><span class="special">(</span><span class="identifier">ValueT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">v</span><span class="special">);<br>    </span><span class="special">};<br></span></code></pre>
<a name="parser_id__checking_and_setting"></a>
<h3>parser_id, checking and setting</h3>
<p> If a node is generated by a rule, it will have an <tt>id</tt> set. Each rule 
  has an id that it sets of all nodes generated by that rule. The id is of type 
  <tt><a href="rule.html#tag">parser_id</a></tt>. The default id of each rule 
  is set to the address of that rule (converted to an integer). This is not always 
  the most convenient, since the code that processes the tree may not have access 
  to the rules, and may not be able to compare addresses. So, you can override 
  the default id used by each rule by <a href="rule.html#tag">giving it a specific 
  ID</a>. Then, when processing the tree you can call <tt>node_val_data::id()</tt> 
  to see which rule created that node.</p>
<a name="structure_layout_of_a_parse_tree"></a>
<h2>structure/layout of a parse tree</h2>
<a name="parse_tree_layout"></a>
<h3>parse tree layout</h3>
<p> The tree is organized by the rules. Each rule creates a new level in the tree.
  All parsers attached to a rule create a node when a successful match is made.
  These nodes become children of a node created by the rule. So, the following
  code:</p>
<pre>    <code><span class="identifier">rule_t </span><span class="identifier">myrule </span><span class="special">= </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'a'</span><span class="special">) </span><span class="special">&gt;&gt; </span><span class="literal">',' </span><span class="special">&gt;&gt; </span><span class="special">*</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'b'</span><span class="special">);<br>    </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a,bb"</span><span class="special">;<br>    </span><span class="identifier">scanner_t </span><span class="identifier">scanner</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">input </span><span class="special">+ </span><span class="identifier">strlen</span><span class="special">(</span><span class="identifier">input</span><span class="special">));<br>    </span><span class="identifier">tree_match</span><span class="special">&lt;&gt; </span><span class="identifier">m </span><span class="special">= </span><span class="identifier">myrule</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">scanner</span><span class="special">);<br></span></code></pre>
<p> When executed, this code would return a tree_match, m. <tt>m.trees[0]</tt> 
  would contain a tree like this:</p>
<table border="0" align="center">
  <tbody><tr>
    <td><img src="theme/trees1.png" width="253" height="151"></td>
  </tr>
</tbody></table>
<p> The root node would not contain any text, and it's id would be set to the
  address of myrule. It would have four children. Each child's id would be set
  to the address of myrule, would contain the text as shown in the diagram, and
  would have no children.</p>
<a name="ast_layout"></a>
<h2>ast layout</h2>
<p> When calling <a href="#ast_parse">ast_parse</a>, the tree gets generated differently.
  It mostly works the same as when generating a parse tree. The difference happens
  when a rule only generated one sub-node. Instead of creating a new level, <a href="#ast_parse">ast_parse</a>
  will not create a new level, it will just leave the existing node. So, this
  code:</p>
<pre>    <code><span class="identifier">rule_t </span><span class="identifier">myrule </span><span class="special">= </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'a'</span><span class="special">);<br>    </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a"</span><span class="special">;<br>    </span><span class="identifier">ast_scanner_t </span><span class="identifier">scanner</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">input</span><span class="special">+</span><span class="identifier">strlen</span><span class="special">(</span><span class="identifier">input</span><span class="special">));<br>    </span><span class="identifier">tree_match</span><span class="special">&lt;&gt; </span><span class="identifier">m </span><span class="special">= </span><span class="identifier">myrule</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">scanner</span><span class="special">);<br></span></code></pre>
<p> will generate a single node that contains 'a'. If <tt>tree_match_policy</tt> 
  had been used instead of <tt>ast_match_policy</tt>, the tree would have looked 
  like this:</p>
<table border="0" align="center">
  <tbody><tr>
    <td><img src="theme/trees2.png" width="139" height="151"></td>
  </tr>
</tbody></table>
<p> ast_match_policy has the effect of eliminating intermediate rule levels which
  are simply pass-through rules. This is not enough to generate abstract syntax
  trees, <a href="#root_node_d_and_ast_generation">root_node_d</a> is also needed. <a href="#root_node_d_and_ast_generation">root_node_d</a>
  will be explained later.</p>
<a name="switching__gen_pt_node_d____amp__gen_ast_node_d__"></a>
<h2>switching: gen_pt_node_d[] &amp; gen_ast_node_d[]</h2>
<p> If you want to mix and match the parse tree and ast behaviors in your application, 
  you can use the <tt>gen_pt_node_d[]</tt> and <tt>gen_ast_node_d[]</tt> directives. 
  When parsing passes through the <tt>gen_pt_node_d</tt> directive, parse tree 
  creation behavior is turned on. When the <tt>gen_ast_node_d</tt>
directive is    used, the enclosed parser will generate a tree using the
ast behavior. Note    that you must pay attention to how your rules are declared
if you use a rule inside of these    directives. &nbsp;The match policy of
the scanner will have to correspond to the desired behavior. &nbsp;If you
avoid rules and use primitive parsers or grammars, then you will not have
problems.</p>
<a name="directives"></a>
<h2>Directives</h2>
<p> There are a few more directives that can be used to control the generation 
  of trees. These directives only effect tree generation. Otherwise, they have 
  no effect.<br>
</p>
<a name="no_node_d"></a>
<h3>no_node_d</h3>
<p> This directive is similar to <tt>gen_pt_node_d</tt> and <tt>gen_ast_node_d</tt>, 
  in that is modifies the scanner's match policy used by the enclosed parser. As it's name 
  implies, it does no tree generation, it turns it off completely. This is useful 
  if there are parts of your grammar which are not needed in the tree. For instance: 
  keywords, operators (<tt>*</tt>, <tt>-</tt>, <tt>&amp;&amp;</tt>, etc.) By eliminating 
  these from the tree, both memory usage and parsing time can be lowered. This 
  directive has the same requirements with respect to rules as <tt>gen_pt_node_d</tt> 
  and <tt>gen_ast_node_d</tt> do. See the example file xml_grammar.hpp (in libs/spirit/example/application/xml 
  directory) for example 
  usage of <tt>no_node_d[]</tt>.</p>
<a name="discard_node_d"></a>
<h3>discard_node_d</h3>
<p> This directive has a similar purpose to <tt>no_node_d</tt>, but works differently. 
  It does not switch the scanner's match policy, so the enclosed parser still generates 
  nodes. The generated nodes are discarded and do not appear in the tree. Using 
  <tt>discard_node_d</tt> is slower than <tt>no_node_d</tt>, but it does not suffer 
  from the drawback of having to specify a different rule type for any rule inside 
  it.</p>
<a name="leaf_node_d_token_node_d"></a>
<h3>leaf_node_d/token_node_d</h3>
<p> Both <tt>leaf_node_t</tt> and <tt>token_node_d</tt> work the same. They 
    create a single node for the match generated by the enclosed parser. 
    Unlike with earlier versions of Spirit, this directive is an implicit
    lexeme and alters the scanner (see 
    <a href="faq.html#scanner_business">Scanner Business</a>). </p>
<h3>reduced_node_d</h3>
<p> This directive groups together all the nodes generated by the enclosed parser. 
    For earlier versions of Spirit <tt>leaf_node_d</tt> and <tt>token_node_d</tt>
    were implemented this way. The new implementation of those directives is a
    lot faster, so <tt>reduced_node_d</tt> is primarily provided for portability
    and can be useful when using a custom node factory (see advanced tree 
    generation, below).</p>
<h3>infix_node_d</h3>
<p> This is useful for removing separators from lists. It discards all the nodes
  in even positions. Thus this rule:</p>
<pre>    <code><span class="identifier">rule_t </span><span class="identifier">intlist </span><span class="special">= </span><span class="identifier">infix_node_d</span><span class="special">[ </span><span class="identifier">integer </span><span class="special">&gt;&gt; </span><span class="special">*(</span><span class="literal">',' </span><span class="special">&gt;&gt; </span><span class="identifier">integer</span><span class="special">) </span><span class="special">];</span></code></pre>
<p> would discard all the comma nodes and keep all the integer nodes.</p>
<a name="discard_first_node_d"></a>
<h3>discard_first_node_d</h3>
<p> This discards the first node generated.</p>
<a name="discard_last_node_d"></a>
<h3>discard_last_node_d</h3>
<p> This discards the last node generated.</p>
<a name="inner_node_d"></a>
<h3>inner_node_d</h3>
<p> This discards the first and last node generated.</p>
<a name="root_node_d_and_ast_generation"></a> 
<h2>root_node_d and ast generation</h2>
<p> The <tt>root_node_d</tt> directive is used to help out ast generation. It 
  has no effect when generating a parse tree. When a parser is enclosed in <tt>root_node_d</tt>, 
  the node it generates is marked as a root. This affects the way it is treated 
  when it's added to the list of nodes being generated. Here's an example:</p>
<pre>    <code><span class="identifier">rule_t </span><span class="identifier">add </span><span class="special">= </span><span class="identifier">integer </span><span class="special">&gt;&gt; </span><span class="special">*(</span><span class="identifier">root_node_d</span><span class="special">[ </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'+'</span><span class="special">) </span><span class="special">] </span><span class="special">&gt;&gt; </span><span class="identifier">integer</span><span class="special">);</span></code></pre>
<p> When parsing 5+6 the following tree will be generated:</p>
<table border="0" align="center">
  <tbody><tr>
    <td><img src="theme/trees3.png"></td>
  </tr>
</tbody></table>
<p> When parsing 1+2+3 the following will be generated:</p>
<table border="0" align="center">
  <tbody><tr>
    <td><img src="theme/trees4.png"></td>
  </tr>
</tbody></table>
<p> When a new node is created the following rules are used to determine how the
  tree will be generated:</p>
<pre><code>    Let a be the previously generated node. <br>    Let b be the new node.<br><br>    If b is a root node then<br><br>        b's children become a + b's previous children. <br>        a is the new first child of b.<br><br>    else if a is a root node and b is not, then<br><br>        b becomes the last child of a.<br><br>    else<br><br>        a and b become siblings.</code></pre>
<p> After parsing leaves the current rule, the root node flag on the top node
  is turned off. This means that the root_node_d directive only affects the current
  rule.</p>
<p> <img height="16" width="15" src="theme/lens.gif"> The example <a href="../example/fundamental/ast_calc.cpp">ast_calc.cpp</a>  demonstrates the use of root_node_d and <a href="#ast_parse">ast_parse</a>. The full source code can be <a href="../example/fundamental/ast_calc.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
<a name="parse_tree_iterator"></a>
<h2>parse_tree_iterator</h2>
<p> The <tt>parse_tree_iterator</tt> class allows you to parse a tree using spirit. 
  The class iterates over the tokens in the leaf nodes in the same order they 
  were created. The <tt>parse_tree_iterator</tt> is templated on <tt>ParseTreeMatchT</tt>. 
  It is constructed with a container of trees, and a position to start. Here is 
  an example usage:</p>
<pre>    <code><span class="identifier">rule_t </span><span class="identifier">myrule </span><span class="special">= </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'a'</span><span class="special">);<br>    </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a"</span><span class="special">;<br><br>    </span><span class="comment">// generate parse tree<br>    </span><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt; </span><span class="identifier">i </span><span class="special">= </span><span class="identifier">pt_parse</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">myrule</span><span class="special">);<br><br>    </span><span class="keyword">typedef </span><span class="identifier">parse_tree_iterator</span><span class="special">&lt;</span><span class="identifier">tree_match</span><span class="special">&lt;&gt; </span><span class="special">&gt; </span><span class="identifier">parse_tree_iterator_t</span><span class="special">;<br><br>    </span><span class="comment">// create a first and last iterator to work off the tree<br>    </span><span class="identifier">parse_tree_iterator_t </span><span class="identifier">first</span><span class="special">(</span><span class="identifier">i</span><span class="special">.</span><span class="identifier">trees</span><span class="special">, </span><span class="identifier">i</span><span class="special">.</span><span class="identifier">trees</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br>    </span><span class="identifier">parse_tree_iterator_t </span><span class="identifier">last</span><span class="special">;<br><br>    </span><span class="comment">// parse the tree<br>    </span><span class="identifier">rule</span><span class="special">&lt;</span><span class="identifier">parse_tree_iterator_t</span><span class="special">&gt; </span><span class="identifier">tree_parser </span><span class="special">=...<br>    </span><span class="identifier">tree_parser</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special">);<br></span></code></pre>
<p> <a name="advanced_tree_generation"></a>
</p>
<h2>advanced tree generation</h2>
<a name="node_value"></a>
<h3>node value</h3>
<p> The <tt>node_val_data</tt> can contain a value. By default it contains a <tt>void_t</tt>, 
  which is an empty class. You can specify the type, using a template parameter, 
  which will then be stored in every node. The type must be default constructible, 
  and assignable. You can get and set the value using</p>
<pre>    <code><span class="identifier">ValueT </span><span class="identifier">node_val_data</span><span class="special">::</span><span class="identifier">value</span><span class="special">;</span></code></pre>
<p> and</p>
<pre>    <code><span class="keyword">void </span><span class="identifier">node_val_data</span><span class="special">::</span><span class="identifier">value</span><span class="special">(</span><span class="identifier">Value </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">value</span><span class="special">);</span></code></pre>
<p> To specify the value type, you must use a different <a href="#node_val_data">node_val_data 
  </a>factory than the default. The following example shows how to modify the factory to store and retrieve a double inside each <span class="identifier">node_val_data</span>.
<pre>    <span class=keyword>typedef </span><span class=identifier>node_val_data_factory</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt; </span><span class=identifier>factory_t</span><span class=special>;<br>    </span><span class=identifier>my_grammar </span><span class=identifier>gram</span><span class=special>;<br>    </span><span class=identifier>my_skip_grammar </span><span class=identifier>skip</span><span class=special>;<br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>iterator_t</span><span class=special>, </span><span class=identifier>factory_t</span><span class=special>&gt; </span><span class=identifier>i </span><span class=special>= <br>        </span><span class=identifier>ast_parse</span><span class=special>&lt;</span><span class=identifier>factory_t</span><span class=special>&gt;(</span><span class=identifier>first</span><span class=special>, </span><span class=identifier>last</span><span class=special>, </span><span class=identifier>gram</span><span class=special>, </span><span class=identifier>skip</span><span class=special>);<br>    // access the double in the root node<br>    </span><span class=keyword>double </span><span class=identifier>d </span><span class=special>= </span><span class=identifier>i</span><span class=special>.</span><span class=identifier>trees</span><span class=special>.</span><span class=identifier>begin</span><span class=special>()-&gt;</span><span class=identifier>value</span><span class=special>;<br></span></pre>
</p>
<a name="access_node_d"></a>
<h3>access_node_d</h3>
<p> Now, you may be wondering, "What good does it do to have a value I can 
  store in each node, but not to have any way of setting it?" Well, that's 
  what <tt>access_node_d</tt> is for. <tt>access_node_d</tt> is a directive. It 
  allows you to attach an action to it, like this:</p>
<pre>    <code><span class="identifier">access_node_d</span><span class="special">[...</span><span class="identifier">some </span><span class="identifier">parsers</span><span class="special">...][</span><span class="identifier">my_action</span><span class="special">()]</span></code></pre>
<p> The attached action will be passed 3 parameters: A reference to the root node
  of the tree generated by the parser, and the current first and last iterators.
  The action can set the value stored in the node.</p>
<a name="tree_node_factories"></a>
<h3>Tree node factories</h3>
<p> By setting the factory, you can control what type of nodes are created and 
  how they are created. There are 3 predefined factories: <tt>node_val_data_factory</tt>, 
  <tt>node_all_val_data_factory</tt>, and <tt>node_iter_data_factory</tt>. You 
  can also create your own factory to support your own node types.</p>
<p> Using factories with grammars is quite easy, you just need to specify the factory type as explicit template parameter to the free ast_parse function:</p>
<pre>    <span class=keyword>typedef </span><span class=identifier>node_iter_data_factory</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt; </span><span class=identifier>factory_t</span><span class=special>;<br>    </span><span class=identifier>my_grammar </span><span class=identifier>gram</span><span class=special>;<br>    </span><span class=identifier>my_skip_grammar </span><span class=identifier>skip</span><span class=special>;<br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>iterator_t</span><span class=special>, </span><span class=identifier>factory_t</span><span class=special>&gt; </span><span class=identifier>i </span><span class=special>= <br>        </span><span class=identifier>ast_parse</span><span class=special>&lt;</span><span class=identifier>factory_t</span><span class=special>&gt;(</span><span class=identifier>first</span><span class=special>, </span><span class=identifier>last</span><span class=special>, </span><span class=identifier>gram</span><span class=special>, </span><span class=identifier>skip</span><span class=special>);<br></span></pre>
<p> Instead, using the factory directly with rules is slightly harder because the 
  factory is a template parameter to the scanner match policy, so you must use a 
  custom scanner:</p>
<pre>    <code><span class="keyword">typedef </span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">void_t </span><span class="identifier">value_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">node_val_data_factory</span><span class="special">&lt;</span><span class="identifier">value_t</span><span class="special">&gt; </span><span class="identifier">factory_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </span><span class="identifier">match_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">ast_match_policy</span><span class="special">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </span><span class="identifier">match_policy_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special">&lt;</span><span class="identifier">iterator_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="identifier"></span><span class="special">&lt;</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special">&gt;</span></code><code><span class="identifier"></span><span class="special"> &gt;</span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special">&lt;</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">&gt; </span><span class="identifier">rule_t</span><span class="special">;<br><br>    </span><span class="identifier">rule_t </span><span class="identifier">r </span><span class="special">=...;<br><br></span></code><code><span class="special">    </span><span class="identifier">scanner_t </span><span class="identifier">scan </span><span class="special">= </span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special"></span><span class="identifier"></span><span class="special">);<br></span></code><code><span class="special"></span></code><code><span class="special">    </span><span class="identifier">match_t </span><span class="identifier">hit </span><span class="special">= </span><span class="identifier">r</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier"></span><span class="special"></span><span class="identifier"></span><span class="special"></span><span class="identifier">scan</span><span class="special">);</span></code></pre>
<a name="node_val_data_factory"></a>
<h3>node_val_data_factory</h3>
<p> This is the default factory. It creates <tt>node_val_data</tt> nodes. Leaf 
  nodes contain a copy of the matched text, and intermediate nodes don't. <tt>node_val_data_factory</tt> 
  has one template parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type 
  of value that will be stored in the <tt>node_val_data</tt>.</p>
<a name="node_all_val_data_factory"></a>
<h3>node_all_val_data_factory</h3>
<p> This factory also creates <tt>node_val_data</tt>. The difference between it 
  and <tt>node_val_data_factory</tt> is that <b>every</b> node contains all the 
  text that spans it. This means that the root node will contain a copy of the 
  entire parsed input sequence. <tt>node_all_val_data_factory</tt> has one template 
  parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type of value that 
  will be stored in the <tt>node_val_data</tt>.</p>
<a name="node_iter_data_factory"></a>
<h3>node_iter_data_factory</h3>
<p> This factory creates the <tt>parse_tree_iter_node</tt>. This node stores iterators 
  into the input sequence instead of making a copy. It can use a lot less memory. 
  However, the input sequence must stay valid for the life of the tree, and it's 
  not a good idea to use the <tt>multi_pass</tt> iterator with this type of node. 
  All levels of the tree will contain a begin and end iterator. <tt>node_iter_data_factory</tt> 
  has one template parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type 
  of value that will be stored in the node_val_data.</p>
<a name="custom"></a>
<h3>custom</h3>
<p> You can create your own factory. It should look like this:</p>
<pre>    <code><span class="keyword">class </span><span class="identifier">my_factory<br>    </span><span class="special">{<br>    </span><span class="keyword">public</span><span class="special">:<br><br>        </span><span class="comment">// This inner class is so that the factory can simulate<br>        // a template template parameter<br><br>        </span><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">&gt;<br>        </span><span class="keyword">class </span><span class="identifier">factory<br>        </span><span class="special">{<br>        </span><span class="keyword">public</span><span class="special">:<br><br>            </span><span class="comment">// This is your node type<br>            </span><span class="keyword">typedef </span><span class="identifier">my_node_type </span><span class="identifier">node_t</span><span class="special">;<br><br>            </span><span class="keyword">static </span><span class="identifier">node_t </span><span class="identifier">create_node</span><span class="special">(<br>                </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">last</span><span class="special">, </span><span class="keyword">bool </span><span class="identifier">is_leaf_node</span><span class="special">)<br>            </span><span class="special">{<br>                </span><span class="comment">// create a node and return it.<br>            </span><span class="special">}<br><br>            </span><span class="comment">// This function is used by the reduced_node directive.<br>            // If you don't use it, then you can leave this function<br>            // unimplemented.<br><br>            </span><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">ContainerT</span><span class="special">&gt;<br>            </span><span class="keyword">static </span><span class="identifier">node_t </span><span class="identifier">group_nodes</span><span class="special">(</span><span class="identifier">ContainerT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">nodes</span><span class="special">)<br>            </span><span class="special">{<br>                </span><span class="comment">// Group all the nodes into one and return it.<br>            </span><span class="special">}<br>        </span><span class="special">};<br>    </span><span class="special">};<br><br><br>    </span><span class="comment">// Typedefs to use my_factory<br>    </span><span class="keyword">typedef </span><span class="identifier">my_factory </span><span class="identifier">factory_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </span><span class="identifier">match_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">tree_match_policy</span><span class="special">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </span><span class="identifier">match_policy_t</span><span class="special">;<br></span></code><code><span class="special"><br>    </span><span class="comment">// Typedefs if you are using rules instead of grammars<br></span></code><code><span class="special">    </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special">&lt;</span><span class="identifier">iterator_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="identifier"></span><span class="special">&lt;</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special">&gt;</span></code><code><span class="identifier"></span><span class="special"> &gt;</span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br>    </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special">&lt;</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">&gt; </span><span class="identifier">rule_t</span><span class="special">;<br></span></code><code><span class="special"></span><span class="special"><br></span></code></pre><table border="0"><tbody><tr><td width="10"><br>
</td>
    <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
    <td width="30"><a href="symbols.html"><img src="theme/l_arr.gif" border="0"></a></td>
    <td width="30"><a href="multi_pass.html"><img src="theme/r_arr.gif" border="0"></a></td>
  </tr>
</tbody></table>
<hr size="1">
<p class="copyright">Copyright &copy; 2001-2002 Daniel C. Nuffer<br>Revised 2007 Copyright &copy; Tobias Schwinger<br>
  <br>
  <font size="2">Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)</font></p>
<p class="copyright">&nbsp;</p>
<br>
</body></html>
